from typing import List


class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # 计算每个被限制位置的实际最大高度：正反向遍历
        marks = [[1, 0]] + sorted(restrictions)
        size = len(marks)
        for i in range(size - 1):
            marks[i + 1][1] = min(marks[i + 1][1], marks[i][1] + (marks[i + 1][0] - marks[i][0]))
        for i in range(size - 1, 0, -1):
            marks[i - 1][1] = min(marks[i - 1][1], marks[i][1] + (marks[i][0] - marks[i - 1][0]))

        # 计算每一段的最大值（不包括最后一段）
        ans = 0
        for i in range(size - 1):
            i1, h1 = marks[i]
            i2, h2 = marks[i + 1]

            distance = i2 - i1 - 1
            distance -= max(h1, h2) - min(h1, h2)  # 先将更低的与更高的取平

            ans = max(ans, max(h1, h2) + (distance + 1) // 2)

        # 计算最后一段
        i, h = marks[-1]
        ans = max(ans, h + (n - i))

        return ans


if __name__ == "__main__":
    print(Solution().maxBuilding(n=5, restrictions=[[2, 1], [4, 1]]))  # 2
    print(Solution().maxBuilding(n=6, restrictions=[]))  # 5
    print(Solution().maxBuilding(n=10, restrictions=[[5, 3], [2, 5], [7, 4], [10, 3]]))  # 5
